Московская олимпиада по информатике - 2005
Здесь размещены задачи очного тура 2005/06 учебных годов. Условия задач доступны на официальном сайте олимпиады: olympiads.ru.
Задача A. Триангуляция
[править]Автор задачи и разбора — В. М. Гуровиц
Решение задачи разбивается на две части: нужно сначала определить, есть ли не треугольные части, а затем найти одну из них.
Первая часть решения реализуется просто: N-угольник разбивается непересекающимися диагоналями на треугольники тогда и только тогда, когда количество диагоналей равно N-3. Это несложно доказать, сравнив сумму углов N-угольника с суммой углов треугольников, на которые он разбивается диагоналями.
Если же диагоналей меньше, чем N-3, то в многоугольнике есть хотя бы одна не треугольная грань. Ее поиском мы сейчас и займемся.
Разберем решение задачи на примере 10-угольника с вершинами 1, 2, 3, …, 9, 10 и диагоналями 1 — 6, 2 — 4, 4 — 6, 1 — 7, 7 — 10. Поскольку решение не зависит от того, как именно мы изобразим данный выпуклый многоугольник, расположим его на плоскости таким образом, как показано на рисунке: сторону 1 — 10 расположим горизонтально, а остальные вершины расположим над этой стороной.
Спроецируем все стороны и диагонали на горизонтальную прямую и далее будем рассматривать только эти проекции. Заметим, что поскольку стороны и диагонали многоугольника не пересекались, то и их проекции не пересекаются, то есть любые два отрезка-проекции либо не имеют внутренних точек, либо один из отрезков лежит внутри другого. Назовем отрезок 1 — 10 отрезком уровня 1. Максимальные отрезки, на которые он разбивается (1 — 7 и 7 — 10) назовем отрезками уровня 2. Отрезки, на которые разбиваются отрезки второго уровня, назовем отрезками третьего уровня (отрезок 1 — 7 разбивается на отрезки 1 — 6, 6 — 7). Отрезки третьего уровня в свою очередь разбиваются на отрезки четвертого уровня и т. д. Заметим, что на последних уровнях присутствуют только отрезки длины 1 — проекции сторон многоугольника.
Рассмотрим одну из частей, на которые диагонали разбивают многоугольник, например, 1 — 2 — 4 — 6. Одна из ее сторон (1 — 6) является отрезком третьего уровня, а остальные — это все отрезки четвертого уровня, на которые разбивается отрезок 1 — 6. Так устроена любая из частей, как треугольная, так и не треугольная. Таким образом, для того, чтобы найти не треугольную часть, достаточно найти отрезок, который разбивается на три или более отрезков следующего уровня. В нашем примере таких отрезка два: кроме отрезка 1 — 6 есть еще отрезок 7 — 10.
Перейдем к обсуждению реализации описанной идеи. Будем идти слева направо по горизонтальной прямой, на которую спроецированы все отрезки, и следить за началами и концами отрезков (см. рис.). Обратите внимание: каждый раз, когда мы встречаем начало отрезка, мы опускаемся на один уровень вниз, а когда мы встречаем конец отрезка, мы поднимаемся на один уровень вверх. Таким образом, нас интересует лишь, сколько начал и сколько концов отрезков проектируется в каждую из точек 1, 2, 3, … на горизонтальной оси. (Началом мы считаем вершину с меньшим номером). Определить это можно при считывании входных данных из файла. Пусть o[i] — количество начал, а c[i] — количество концов отрезков, проектирующихся в точку i. Заметим, что в каждую из точек 2, …, n-1 проектируется одно начало и один конец стороны многоугольника, в точку 1 проектируется два начала сторон, а в точку n — два конца. Напишем соответствующий код:
o[1]:=2; for i:=2 to n-1 do o[i]:=1; o[n]:=0; c[1]:=0; for i:=2 to n do c[i]:=1; c[n]:=2;
Далее будем читать диагонали из входного файла и подсчитывать начала и концы:
for i:=1 to M do begin
read(a,b);
if a>b then begin inc(o[b]);inc(c[a]); end
else begin inc(o[a]);inc(c[b]); end;
end;
Переходим к реализации основной части алгоритма. Будем двигаться слева направо, просматривая в каждой точке сначала все концы, а затем все начала отрезков. Введем переменную level, в которой будем хранить текущий уровень отрезка.
level:=0;
for i:=1 to n do begin
for j:=1 to c[i] do begin
{Обрабатываем конец отрезка}
end;
for j:=1 to o[i] do begin
{Обрабатываем начало отрезка}
end;
end;
Что происходит, когда мы встречаем конец отрезка на уровне level? Нам хочется узнать, на сколько отрезков был разбит этот отрезок. Если он был разбит лишь на два отрезка, то мы встретили треугольную грань, которая нас не интересует. Если он был отрезком последнего уровня, и не разбивался на отрезки, то он нас также не интересует. Если же этот отрезок был разбит на три или более отрезков следующего уровня, то мы нашли не треугольную грань. Таким образом, нам необходимо хранить количество отрезков, встретившихся нам на уровне level — обозначим это число l[level]. О том, как его вычислять, мы поговорим чуть позже. Напишем соответствующий код:
if (l[level+1])>2 then begin <печатаем найденную многоугольную часть> exit; end
Если мы не нашли требуемую многоугольную часть, то мы обнуляем количество отрезков, найденных на уровне level+1 (они нам больше не нужны), и поднимаемся на один уровень вверх:
else begin l[level+1]:=0; dec(level); end;
О том, как печатать многоугольную часть, мы поговорим чуть позже.
А что происходит, когда мы встречаем начало отрезка? Мы должны, во-первых, увеличить уровень на 1, а во-вторых, увеличить количество найденных на этом уровне отрезков на 1:
inc(depth); inc(l[depth]);
Еще раз подчеркнем: на каждом уровне level+1 мы считаем количество отрезков, являющихся частями одного и того же отрезка на уровне level. Как только отрезок на уровне level заканчивается, мы проверяем, на сколько частей он разбит, и если количество этих частей не больше двух, обнуляем l[level+1].
Пока мы еще не научились хранить и печатать нужные нам отрезки. Но прервемся ненадолго и оценим, какие ресурсы требует наша программа. Поскольку количество диагоналей не превосходит количества вершин, для хранений начал и концов всех отрезков нам понадобится массив, длина которого пропорциональна количеству вершин многоугольника N. Для заполнения этих массивов нам понадобится порядка N операций. Таким образом, наш алгоритм работает за линейное относительно N время и использует память, также пропорциональную N. Мы постараемся, заканчивая реализацию алгоритма, не выходить за указанные ограничения. Итак, нам нужно запоминать встречающиеся вершины. Достаточно запоминать только начала отрезков. Будем на каждом уровне запоминать в массиве first[level] первое встретившееся начало отрезка, в массиве second[level] — второе встретившееся начало, а в массиве next[k] — k-е встретившееся начало любого уровня:
if l[level]=1 then first[level]:=i;
if l[level]=2 then second[level]:=i;
if l[level]>2 then next[l[level]]:=i;
На первый взгляд может показаться странным, что, скажем, 3-е по счету начало на любом уровне мы записываем в один и тот же элемент одного и того же массива, затирая тем самым информацию обо всех ранее найденных третьих началах. Но на самом деле она нам и не нужна. Пусть мы встретили конец некоторого отрезка на уровне level, и оказалось, что он разбит не менее чем на три части. Это значит, что каждая из этих частей в свою очередь разбита менее чем на три части (иначе мы бы остановились, дойдя до конца соответствующего отрезка), и каждая из частей этих частей также разбита менее чем на три части и т. д. Таким образом, с тех пор как мы встретили третий (четвертый, пятый, …) отрезок на уровне level+1, мы более не встречали третьих (четвертых, пятых, …) отрезков, то есть в массиве next хранятся номера вершин, служащих началами отрезков именно на уровне level+1. Таким образом, мы обходимся всего тремя дополнительными массивами first, second и next длины порядка N каждый. Теперь несложно вывести вершины многоугольной части, дополнив фрагмент программы, написанный нами выше:
if (l[level+1])>2 then begin
{печатаем найденную многоугольную часть}
write(i,' ',first[level+1],' ',second[level+1],' ');
for k:=3 to l[level+1] do write(next[k],' ');
exit;
end
Осталось объяснить, зачем мы печатаем число i. Дело в том, что кроме начал всех отрезков есть еще одна вершина, которая является вершиной нашей многоугольной части — самая правая вершина. Это как раз последний встреченный нами конец отрезка, то есть вершина с номером i.
Существует множество других алгоритмов, решающих задачу за время O(N log N) или O(N²), что удовлетворяет приведенным в задаче ограничениям. Но реализация этих алгоритмов не проще, а зачастую сложнее приведенной в этом разборе реализации линейного алгоритма.
Задача B. Палиндром
[править]Автор разбора — В. М. Гуровиц
Подсчитаем, сколько раз во входном файле встречается каждая буква. Для этого можно воспользоваться массивом:
k : array ['A'..'Z'] of longint;
Соответствующая часть программы будет выглядеть примерно так:
readln(N); for i:=1 to N do begin read(ch); Inc(k[ch]); end;
Если в палиндроме общее количество символов четно, то для каждого символа найдется симметричный ему, поэтому каждая буква должна встречаться четное количество раз. Если же общее количество символов нечетно, то для каждого символа, кроме стоящего в центре палиндрома, найдется пара, поэтому все буквы кроме одной, должны встречаться четное число раз. Таким образом, если некоторая буква встречается во входном файле четное число раз, то мы можем использовать все ее вхождения, а из букв, которые встречаются нечетное число раз лишь одну (первую по алфавиту) мы сможем использовать нечетное число раз. Определим, какая буква встречается нечетное количество раз первой:
o:='-'; {Буква, встречающаяся нечетное число раз}
for ch:='Z' to 'A' do
if k[ch] mod 2=1 then o:=ch;
Если во входном файле нет букв, встречающихся нечетное число раз, то первый по алфавиту палиндром устроен следующим образом: сначала идет половина букв A, затем половина букв B, …, затем половина букв Z, далее вторая половина букв Z, вторая половина букв Y, …, вторая половина букв A:
if o='-' then begin
for ch:='A' to 'Z' do
for i:=1 to k[ch] div 2 do
write(ch);
for ch:='Z' downto 'A' do
for i:=1 to k[ch] div 2 do
write(ch);
end;
Если во входном файле есть буквы, встречающиеся нечетное число раз, то первый по алфавиту палиндром устроен так же, как и палиндром четной длины, за одним исключением: в центре палиндрома расположена буква, записанная в переменную o:
if o<>'-'; then begin
for ch:='A' to 'Z' do
for i:=1 to k[ch] div 2 do
write(ch);
write(o);
for ch:='Z' downto 'A' do
for i:=1 to k[ch] div 2 do
write(ch);
end;
Задача C. Представление числа
[править]Автор задачи и разбора — А. Ю. Гусаков
Задача решается применением метода динамического программирования. Прежде чем перейти к описанию идеи решения, введем несколько определений.
Будем называть выражение C выражением первого типа, если оно является числом от 1 до K или если последней операцией при его вычислении является сложение, то есть, C = A + B, где A и B — некоторые выражения.
Будем называть выражение C выражением второго типа, если оно является числом от 1 до K или если последней операцией при его подсчете является умножение, то есть, C = A * B, где A и B — некоторые выражения. Например, (2+3*4)+5*7 — выражение первого типа, (2+3)*(3+2) — выражение второго типа, 1 — выражение, относящееся как к первому, так и ко второму типу.
Теперь обсудим идею решения. Пусть a[1,m] равно наименьшей длине выражения первого типа, значение которого равно m; a[2,m] равно наименьшей длине выражения второго типа, значение которого равно m. Легко видеть, что при m <= K значения a[1,m] и a[2,m] равны длине числа m. Пусть теперь m > K, и у нас уже вычислены все значения a[1,1], …, a[1,m-1], a[2,1], …, a[2,m-1].
Сначала вычислим a[1,m]. Поскольку соответствующее выражение представимо в виде C=A+B, нам достаточно перебрать все возможные значения и типы выражений A и B и выбрать оптимальную комбинацию. Иными словами, a[1,m]=min(a[i1,t]+a[i2,m-t]+1), где i1, i2 — 1 или 2, а t <= m/2 (можно считать, что значение A меньше или равно m/2, иначе A и B можно поменять местами). В переменных how[1,m][1], how[1,m][2], how[1,m][3] будем хранить те значения i1, t, i2 соответственно, при которых достигается минимальное значение.
Теперь вычислим a[2,m]. Cоответствующее выражение представимо в виде A*B, где A и B — либо выражения второго типа, либо выражения первого типа, взятые в скобки (либо какая-то их комбинация). Будем считать, что значение A меньше или равно, иначе поменяем местами A и B. Таким образом, a[2,m]=min(a[i1,t]+a[i2,m/t]+1+2*(4-i1-i2)), где i1, i2 — 1или 2, а t<= и m делится на t.
Замечание. Число 4-i1-i2 равно количеству выражений первого типа среди A и B, а значит, равно количеству пар скобок, которое придется добавить.
В переменных how[2,m][1], how[2,m][2], how[2,m][3] будем хранить те значения i1, t, i2 соответственно, при которых достигается минимум.
Теперь мы умеем вычислять значения a[1,1], …, a[1,N], a[2,1], …, a[2,N]. Естественно, что искомое выражение является выражением первого или второго типов, поэтому его длина равна min(a[1,N], a[2,N]). Осталось только научиться его выводить. Для этого напишем рекурсивную процедуру Save(last, n), которая будет выписывать выражение типа last, значением которого является n. Во-первых, если n<=K, то нужно просто вывести число cur. Иначе нужно посмотреть на значение last.
Если last=1 (то есть выражение имеет вид A+B), то сначала выпишем первое слагаемое — Save(how[last,n][1],how[last,n][2]) — затем поставим знак '+' и выпишем второе слагаемое — Save(how[last,n][3],n-how[last,n][2]).
Если last=2 (то есть, имеем дело с произведенем), то нужно действовать аналогично случаю last=1, но при этом не забыть, что если какой-то из множителей первого типа, то его надо окружить скобками.
Количество операций, выполняемых алгоритмом, пропорционально N² что удовлетворяет указанным в условии задачи ограничениям.
Приведем теперь полный текст решения с подробными комментариями:
const MaxN=10*1000;
var N,K:LongInt; a:array [1..2,1..MaxN] of LongInt; how:array [1..2,1..MaxN,1..3] of LongInt; m,i1,i2,t:LongInt;
function CountOfDigits(a:LongInt):byte; //подсчитывает количество цифр в числе а var res:LongInt; begin res:=0; while a>0 do begin a:=a div 10; //каждое деление на 10 уменьшает количество цифр на одну inc(res); end; CountOfDigits:=res; end;
procedure Save(last,n:LongInt);//тип выражения и его значение
begin
if (n<=K) and (a[last,n]=CountOfDigits(n)) then
write(n)//если n<=K, просто выводим n
else if last=1 then begin //имеем дело с суммой
Save(how[last,n][1],how[last,n][2]);//выводим первое слагаемое
write('+');
Save(how[last,n][3],n-how[last,n][2]);//выводим второе слагаемое
end else if last=2 then begin //имеем дело с произведением
if how[last,n][1]=1 then write('(');
Save(how[last,n][1],how[last,n][2]);//выводим первый множитель
if how[last,n][1]=1 then write(')');//если он первого типа, то окажется в скобках
write('*');
if how[last,n][3]=1 then write('(');//аналогично поступаем со вторым множителем
Save(how[last,n][3],n div how[last,n][2]);
if how[last,n][3]=1 then write(')');
end;
end;
Begin
read(N,K);
for m:=1 to K do begin //случай m<=K
a[1,m]:=CountOfDigits(m);
a[2,m]:=CountOfDigits(m);
end;
for m:=K+1 to N do begin//случай K<m<=N
// считаем a[1,m] и how[1,m], перебирая i1, i2, t :
a[1,m]:=MaxLongInt;//начальное значение
for t:=1 to (m div 2) do
for i1:=1 to 2 do
for i2:=1 to 2 do
if a[i1,t]+a[i2,m-t]+1<a[1,m] then begin
a[1,m]:=a[i1,t]+a[i2,m-t]+1;
how[1,m][1]:=i1;
how[1,m][2]:=t;
how[1,m][3]:=i2;
end;
// считаем a[2,m] и how[2,m], перебирая i1, i2, t:
a[2,m]:=MaxLongInt;//начальное значение
for t:=1 to trunc(sqrt(m)) do if m mod t=0 then
for i1:=1 to 2 do
for i2:=1 to 2 do
if a[i1,t]+a[i2,m div t]+1+2*(4-i1-i2)<a[2,m] then begin
a[2,m]:=a[i1,t]+a[i2,m div t]+1+2*(4-i1-i2);
how[2,m][1]:=i1;
how[2,m][2]:=t;
how[2,m][3]:=i2;
end;
end;
if a[1,N]<a[2,N] then // выводим выражение наименьшей длины
Save(1,N)
else
Save(2,N);
End.
Это далеко не единственный вариант реализации. Можно было обойтись без рекурсии. Для этого в элементах a[1,m] и a[2,m] надо хранить не длины выражений, а сами выражения (массив how в этом случае вообще не нужен). В конце программы необходимо просто вывести более короткое из выражени a[1,N] и a[2,N].
Можно грубо оценить длину наибольшей строки и понять, что памяти на такую реализацию хватит. В действительности, самая длинная строка при данных в условии ограничениях получается при N=9358, K=1: ее длина всего лишь 83 символа.
Оказывается, что приведенную динамическую схему можно упростить. Достаточно для каждого числа m хранить информацию лишь о самом коротком выражении, независимо от его типа. При этом, если для данного числа самое короткое выражение может быть как выражением типа 1, так и выражением типа 2, то нужно выбирать произведение, а не сумму. Обоснование правильности этого алгоритма оставим читателю.
Задача D. Восстанови многоугольник
[править]Автор задачи и разбора — В. М. Гуровиц
Опишем алгоритм восстановления многоугольника по числам в клетках; из этого алгоритма в частности будет следовать, что решение всегда единственное.
Рассмотрим пример, изображенный на рис. 1.
Будем восстанавливать границы многоугольника, двигаясь сверху вниз. Начнем с верхней строки. Посмотрим на одну из единиц, стоящую в верхней строке. Верхняя сторона этой клетки не может принадлежать границе многоугольника, поскольку, по условию, многоугольник лежит внутри листа бумаги. Боковые стороны этой клетки тоже не могут лежать на границе многоугольника, поскольку их концы выходят на границу листа. Следовательно, многоугольнику принадлежит нижняя сторона клетки, см. рис. 2.
Мы отметили первые участки границы многоугольника. Уменьшим на 1 числа во всех клетках, границами которых эти участки являются (см. рис. 3).
Итак, на первом шаге нашего алгоритма мы восстановили самые верхние горизонтальные стороны нашего многоугольника. Переходим к следующему шагу.
Рассмотрим концы нарисованных нами отрезков. Из каждой из этих точек должна выходить еще одна сторона нашего многоугольника, причем обязательно вниз (см. рис. 4).
Как и на первом шаге, уменьшим соответствующие числа в клетках, прилежащих к нарисованным на этом шаге отрезкам. При этом некоторые числа уменьшаться сразу на 2, поскольку у некоторых клеток мы обвели две стороны (см. рис. 6)
Итак, на втором шаге мы восстановили все вертикальные отрезки, обведенные во второй сверху строке. Переходим снова к горизонтальным отрезкам, спускаясь на одну клетку вниз.
Во второй строке осталась одна единица. Это означает, что нужно обвести отрезок под этой клеткой, и это единственный отрезок данной горизонтали, принадлежащий границе многоугольника. Обводя его, мы уменьшаем на 1 числа в прилежащих клетках (cм. рис. 7).
В этой горизонтали остались две точки, их которых выходит пока только по одному отрезку. На следующем шаге из этих точек проводим вертикальные отрезки вниз, уменьшая числа в клетках (см. рис. 7).
И, наконец, мы спускаемся еще ниже и по единицам в третей строке клеток восстанавливаем последний горизонтальный ряд (см. рис. 8).
Итак, многоугольник восстановлен. Подведем итоги. Наш алгоритм восстанавливает отрезки сторон многоугольника последовательно, сверху вниз, поочередно восстанавливая горизонтальные и вертикальные отрезки каждой строки. При этом для проведения горизонтальных отрезков мы рассматриваем клетки верхней ненулевой строки, в которых стоят единицы, и обводим их нижние стороны, а для восстановления вертикальных отрезков мы ищем все врешины в предыдущей строке, из которых выходит только одна сторона.
Осталось написать программу. Она состоит из трех частей.
I. Чтение файла и сохранение чисел в двумерном массиве a:
read(y,x);
for i:=1 to y do
for j:=1 to x do
read(a[i][j]);
II. Восстановление многоугольника и сохранение горизонтальных и вертикальных отрезков в двумерных массивах v и h соответственно:
for i:=1 to y do begin
{Восстанавливаем горизонтальные отрезки}
for j:=1 to x do
if a[i][j]=1 then begin
h[i][j]:=1;dec(a[i+1][j]);
end;
{Восстанавливаем вертикальные отрезки}
for j:=1 to x do
if h[i][j]+h[i][j-1]+v[i][j]=1 then begin
v[i+1][j]:=1;dec(a[i+1][j]);dec(a[i+1][j-1]);
end;
end;
III. Рисуем полученный многоугольник:
for i:=1 to y-1 do begin
for j:=1 to x do begin
if v[i][j]=1 then write('|') else write(' ');
if h[i][j]=1 then write('_') else write(' ');
end;
writeln;
end;
В приведённой программе мы считывали все числа в двумерный массив. На самом деле в этом нет необходимости: на каждом шаге алгоритма мы используем лишь две последовательные строки чисел, поэтому можно читать строки чисел из файла последовательно, используя лишь два одномерных массива.
Задача E. Распредели призы
[править]Автор задачи — Е. В. Андреева, авторы разбора — Е. В. Андреева и В. М. Гуровиц
Рассмотрим отдельно три случая.
1. Если K четно и N/K нечетно, то распределить призы требуемым образом нельзя. Действительно, если стоимости призов равны 1, 2, 3, …, N, то суммарная стоимость всех призов равна N(N+1)/2, а каждый участник должен получить призы на сумму N(N+1)/2K=(N/K)((N+1)/2). Но поскольку K четно, то и N четно, то есть N+1 не делится на 2.
2. Если N/K четно, то можно раздавать призы змейкой, см. рис. (каждая вертикаль соответствует одной из K команд).
| 1 | 2 | … | K |
| 2K | 2K-1 | … | K+1 |
| 2K+1 | 2K+2 | … | 3K |
| 4K | 4K-1 | … | 3K+1 |
| … | … | … | … |
| N | N-1 | … | N-k+1 |
3. Если K и N/K нечетны, то решение аналогично решению случая 2, лишь первые 3 строки в данной форме записи результата:
| A1 | A3 | A5 | … | A2 | … | … |
| … | … | … | A2k | Ak+1 | Ak+2 | … |
| A3k | A3k-1 | … | … | … | … | A2k+1 |
То есть в первой строке сначала все нечетные, а потом все четные номера от 1 до К, во второй циклически сдвинутые вправо элементы от Ak+1 до A2k, причем Ak+1 под A2.
Исключение составляет случай N=K, когда решение существует, очевидно, лишь при N=K=1.
Отметим, что хотя ограничения задачи позволяли хранить в памяти всю таблицу, можно было выводить ответ сразу, вычисляя числа в столбцах по мере их печати.
Задача F. Монополия
[править]Автор задачи и разбора — А. П. Лахно
Ситуация, рассматриваемая в задаче, описывается неориентированным графом, вершинами которого являются фирмы, а ребра задаются отношением взаимного доверия.
Изначально, вершины, соответствующие согласившимся фирмам, отмечены. Далее, на каждой итерации создается новый список отмеченных вершин: в него включаются те и только те вершины, у которых на предыдущем шаге была хотя бы одна отмеченная смежная вершина.
Рассмотрим ключевые закономерности изменения списка отмеченных вершин.
Пусть на некотором шаге имеются две смежные вершины, хотя бы одна из которых отмечена. Тогда после одной итерации отмеченная вершина может «погаснуть», но после второй она обязательно вновь станет отмеченной. Заметим, что эта вершина заведомо будет попадать в список отмеченных через каждые две итерации.
Если же имеются две отмеченные смежные вершины, то они останутся отмеченными после любого числа итераций.
Первое решение
Основываясь на этих закономерностях, приходим к следующему алгоритму решения задачи. Раскрасим имеющийся граф в два цвета с помощью поиска в глубину: первую вершину каждой компоненты связности красим в белый, все смежные с ней — в черный, все смежные с ними — снова в белый и т. д. Если при этом в какой-то компоненте связности есть цикл нечетной длины, то возникает коллизия: компоненту связности нельзя раскрасить в два цвета так, чтобы все вершины, смежные с белыми, были черными, а все вершины, смежные с черными, — белыми.
Параллельно с раскраской, для каждой вершины запоминаем номер компоненты связности, в которой она лежит. Для компонент связности, содержащих циклы нечетной длины, помечаем, что их раскрасить не удалось. Кроме того, для каждой компоненты связности запоминаем число белых вершин и число черных вершин в ней.
Проходим по первоначальному списку отмеченных вершин.
Если компонента связности, в которой лежит отмеченная вершина, содержит циклы нечетной длины, то, начиная с некоторой итерации, все вершины компоненты будут попадать в список отмеченных на каждом шаге.
Если исходный список отмеченных вершин содержит как белую, так и черную вершину какой-то компоненты связности, то, также как и в предыдущем случае, начиная с некоторой итерации, все вершины компоненты будут попадать в список отмеченных на каждом шаге.
Если список вообще не содержит отмеченных вершин из какой-то компоненты, то ни одна вершина этой компоненты никогда не попадет в список отмеченных.
Для остальных компонент в первоначальном списке содержатся отмеченные вершины только одного цвета (для каждой компоненты — своего). Начиная с некоторой итерации, на каждом четном шаге в список отмеченных попадают вершины таких компонент, отмеченных тем же цветом, что и отмеченные вершины в исходном списке, а на нечетных шагах — вершины противоположного цвета. Единственным исключением здесь компоненты связности, состоящие ровно из одной вершины — эта вершина в любом случае никогда не попадет в список отмеченных после первого шага.
С учетом всего вышесказанного, ответ задачи вычисляется как максимум из трех чисел: количества отмеченных вершин в исходном списке и количеств отмеченных вершин на четных и нечетных шагах с достаточно большим номером, которые в свою очередь несложно вычисляются с помощью ранее посчитанных величин, указанных в начале разбора.
Второе решение
Приведем вариант решения, несколько менее естественного, но существенно более изящного. Построим граф, вершинами которого являются пары вида (четность итерации, номер фирмы), а ребра соединяют вершины с разной четностью, соответствующие взаимно доверяющим фирмам. Пометим исходно вершины, соответствующие четной итерации и изначально согласившимся фирмам. Запустим теперь из помеченных вершин обход в глубину или ширину. Ответом задачи будет максимум из количества изначально согласившихся фирм и количеств обойденных вершин с четным и нечетным числом итераций соответственно.
Асимптотика обоих решений определяется асимптотикой процедуры обхода графа, то есть O(N+M).
В ограничениях задачи было достаточно разумно при отсутствии правильного решения, написать, по крайней мере, решение, моделирующее процесс. При использовании отсечения по времени и аккуратном кодировании такое решение тоже набирало полный балл.
Заметим, что при моделировании, как это ни странно, не достаточно N итераций. Приведем простой пример: цепочка из пяти вершин, у которой, кроме того, соединены пятая и третья вершины. Изначально отмечена только первая вершина. В данном случае ответ достигается лишь на шестой итерации при пяти вершинах. В общем же случае оптимальное решение будет найдено, не более чем за 2N итераций.
Пример
5 1 0 0 0 0 5 1 2 2 3 3 4 4 5 3 5
Задача G. Найди прямую
[править]Автор задачи и разбора — Б. О. Василевский
Степенью прямой назовем количество данных отрезков, которые она пересекает; концы отрезков будем называть вершинами.
Прежде всего, обсудим, каким может быть относительное расположение искомой прямой и данных отрезков. Рассмотрим прямую с максимальной степенью.
1. Если прямая не горизонтальная, будем двигать ее влево горизонтально, пока она не пройдет через какую-нибудь вершину. Иначе можно двигать ее вертикально вверх. Новая прямая будет иметь такую же степень, как и начальная прямая, так как количество пересечений не может увеличиться, а уменьшается оно только при прохождении через концы отрезков.
2. Итак, можно считать, что искомая прямая должна проходить через какую-либо вершину. Теперь будем вращать эту прямую против часовой стрелки вокруг вершины, через которую она проходит, пока прямая не пройдет через вторую вершину. Аналогично, степень полученной прямой равна степени исходной. И теперь прямая проходит через две различных вершины.
На этих идеях основано решение с алгоритмической сложностью O(N³), где N — количество отрезков: перебираем все пары вершин; для каждой пары считаем степень прямой; через эти вершины проходящей; среди них выбираем прямую с наибольшей степенью. Но такое решение не набирает полного балла.
Решение с алгоритмической сложностью O(N² log N) использует только первое рассуждение: искомая прямая проходит через вершину. Таким образом, если для каждой вершины найти прямую наибольшей степени, которая проходит через нее, то выбрав среди всех степеней максимум, получим ответ.
Научимся искать прямую с наибольшей степенью, проходящую через вершину P(xp, yp). Любое упоминание прямой теперь подразумевает, что она проходит через P. Сразу договоримся не рассматривать отрезки, проходящие через P, так как они не влияют на поиск прямой максимальной степени. Главное — не забыть их подсчитать и учесть при вычислении степени прямой.
Общая идея такова: будем вращать прямую y = yp вокруг P против часовой стрелки, считая пересечения.
Ориентированной площадью (A, B) пары векторов A = (x1, y1) и B = (x2, y2) назовем число, равное x1*y2 − y1*x2. По абсолютно величине она равна площади параллелограмма, у которого в качестве сторон взяты A и B, отложенные от одной точки. Она равна нулю тогда и только тогда, когда A и B коллинеарны. В противном случае знак (A, B) дает нам информацию о направлении кратчайшего поворота от вектора A к вектору B. Если система координат выбрана стандартным образом, то (A, B) больше нуля тогда и только тогда, когда кратчайший поворот — против часовой стрелки, см.рис.1 (соответственно, (A, B) меньше нуля тогда и только тогда, когда кратчайший поворот — по часовой стрелке, см. рис. 2).
Назовем началом отрезка XY ту его вершину, которая встретится при вращении нашей прямой раньше остальных точек этого отрезка; концом — ту, которая встретится последней. Это можно определить, вычислив знак ориентированной площади S = (PX, PY): если X — начало, то S > 0. В случае, если X, Y и P лежат на одной прямой, началом будем считать любую из вершин, концом — оставшуюся.
Рассмотрим для начала более простой случай: по отношению к P все отрезки лежат справа и сверху. Чтобы реализовать «вращение прямой», надо отсортировать все вершины по по возрастанию полярного угла (то есть по углу между лучом из точки P в вершину и осью абсцисс), в случае совпадения будем считать, что конец всегда больше начала.
Для тех, кто впервые встретил фразу «сортировка по полярному углу», сделаем небольшие пояснения. Сортировка точек по полярному углу проходит почти также, как и сортировка чисел, только для сравнения двух точек X, Y используется знак ориентированной площади S = (PX, PY). «X меньше Y», если S > 0 («X больше Y», если S < 0).
Прямая y = yp не пересекает ни одного отрезка в силу того, что все вершины лежат выше нее.
Шаг 1. Считаем переменную C равной 0 (значение C будет объяснено чуть ниже).
Шаг 2. Просматриваем все вершины так, как они идут в отсортированном списке.
Для каждой вершины Q (
Если Q – начало, то (
Увеличиваем C на 1.
Если C больше найденного максимума, то обновляем максимум, запоминаем, что соответствующая прямая проходит через Q
) иначе (
Уменьшаем C на 1.
)
)
Понятно, что после просмотра вершины Q степень всех прямых между PQ и PS (где S — следующая за Q вершина в отсортированном списке) равна C (любая из этих прямых пересекает все отрезки, которые уже «начались», но еще не «закончились», их ровно C по построению). Среди всех таких значений C надо выбрать наибольшее. В качестве прямой с соответствующей степенью можно брать, к примеру, PQ, как и описано в алгоритме.
Сложность общего случая (когда отрезки расположены произвольно) заключается в следующем: пусть мы сравниваем точки как обычно — по полярному углу. Тогда привычное свойство сравнения «из a <= b, b <= c, следует a <= c» не выполняется, например, для вершин a = (0, 1), b = (1/2, −1/2), c = (-1/2, −1/2), P = (0, 0). Поэтому любая сортировка за время N log N, основанная на таком свойстве, будет сортировать точки неправильно. А ведь именно за счет сортировки за время N log N мы имеем оценку O(N² log N), а не O(N³).
Существует несколько способов выйти из этой ситуации, но наиболее простой, на наш взгляд, следующий.
Исходная прямая — по-прежнему y = yp. Разделим отрезки на два типа:
- пересекающие y = yp,
- не пересекающие y = yp.
Идея в том, чтобы перед сортировкой подвергать симметрии относительно P все вершины, лежащие ниже P (не забывая, начало это или конец). Но делать такую симметрию надо аккуратно.
Пусть отрезок XY после возможной симметрии его вершин, описанной выше, перешел в отрезок X’Y'. Если ориентированная площадь (PX, PY) отличается по знаку от ориентированной площади (PX', PY'), то визуально начало и конец «поменялись местами» (мы по-прежнему называем X` началом, если X — начало и наоборот — концом, если X — конец). То есть при вращении наша прямая сначала встретит конец X`Y`, а потом начало (см. рис. 3). В этом случае надо учитывать, что прямые из области 3 (см. рис. 3) тоже пересекают XY (в алгоритме — шаг 3). Кстати, такое возможно, только если XY — первого типа.
С отрезками второго типа таких неудобств не будет.
Замечание 1. Если приступать к сортировке, проделав предварительно лишь описанные преобразования, мы не получим правильного порядка. Пусть, например, P(0, 0), A(-1, 0), B(1, 0), A и B — начала. Тогда вершины A и B будут считаться равными (подумайте почему). Чтобы избежать этого, можно подвергать симметрии еще и точки, лежащие на y = yp, но левее P. Тогда никакие две вершины не будут лежать с P на одной прямой и одновременно по разные стороны относительно P.
Замечание 2. Чтобы проверить, лежит ли P на отрезке AB, надо сначала убедиться, что все эти три точки лежат на одной прямой. Если это верно, можно посмотреть скалярное произведение векторов PA и PB: если оно меньше или равно 0, то P принадлежит AB (0 может быть, если один из векторов нулевой), в противном случае — нет.
Для каждой точки X через X' будем обозначать следующее: если X ниже P, или X принадлежит y = yp и левее P, то X' симметрична X относительно P. В противном случае X = X`.
Чтобы алгоритм получился полным, вспомним о существовании отрезков, проходящих через P. По-прежнему считаем, что концы отрезка ему принадлежат.
Шаг 1. Считаем переменную C равной 0 (ее смысл такой же, как и в предыдущем варианте). Список для сортировки считаем пустым.
Шаг 2 (создание списка для сортировки).
Для каждого отрезка XY (
Если P принадлежит XY, то (
Увеличить C на 1
) иначе (
Если XY – первого типа, то (
Если знаки (PX, PY) и (PX', PY') различаются (оба числа должны быть отличны от нуля),
то увеличить C на 1.
)
Пусть S = (PX, PY).
Если S >= 0, то X' помечаем как начало, Y' – как конец.
Если S < 0, то Y' помечаем как начало, X' – как конец.
Добавляем в список X'
Добавляем в список Y'
)
)
Шаг 3 (сортировка и поиск прямой с максимальной степенью). Теперь отсортируем полученный список по полярному углу и будем действовать как в простом случае (единственное отличие — стартовое значение C может быть отлично от нуля).
Задача H. Тупики
[править]Автор задачи — В. А. Матюхин, автора разбора — В. М. Гуровиц
Задача решается моделированием описанного в условии процесса. Будем хранить номера свободных на данный момент тупиков, и список стоящих в тупиках в данный момент электричек (точнее, времена их отправления и номера тупиков, в которых они стоят). Будем читать из файла последовательно информацию о прибывающих электричках. Для каждой прибывающей электрички нам потребуется:
- «отправить в очередной рейс» все электрички, стоящие в тупиках, время отправления которых меньше. чем время прибытия нашей электрички;
- добавить тупики, из которых отправились электрички, к свободным тупикам;
- выбрать свободный тупик с наименьшим номером и поставить туда нашу электричку.
(Описать реализацию с квадратичной сложностью)
Таким образом, нам понадобятся две структуры данных. В первой будут храниться электрички, стоящие в тупиках. С ней мы будем проделывать следующие операции:
- добавлять электричку (эта операция будет выполняться N раз);
- удалять электрички, у которых время отправления меньше данного (тоже N раз).
Заметим, что последнюю операцию можно описать по-другому: удалять электрички с наименьшим временем отправления до тех пор, пока оно меньше данного времени.
Вторая структура данных предназначена для хранения свободных тупиков. С ней мы также будем проделывать две операции:
- добавлять освободившийся тупик;
- удалять тупик с наименьшим номером.
В обоих случаях нам требуется реализовать один и тот же набор операций. То есть мы можем использовать структуры данных одного типа. Такая структура данных называется очередь с приоритетами. Для нее реализуются операции Добавить_элемент и Удалить_наименьший. Если вы пишите программы на языке C++, вы можете воспользоваться реализацией очереди с приоритетами из библиотеки STL (priority_queue из библиотеки queue). Поскольку очередь тупиков (Tup) состоит из целых чисел — номеров тупиков, то ее объявить совсем просто:
priority_queue <int, vector<int>, greater<int> > Tup;
В этом объявлении сказано, что нам нужна очередь приоритетов, элементами которой являются целые числа, которые будут сравниваться операцией > (greater).
Для хранения электричек нам понадобится определить класс Train следующим образом:
class Train {
public:
//время отправления и номер тупика
int outtime, tupik;
//конструкторы
Train () {}
Train (const int o, const int t) : outtime(o), tupik(t) {}
//сравнение производится по времени отправления
bool operator> (const Train & right) const {
return outtime > right.outtime;
}
};
После этого очередь электричек (Tr) определим так:
priority_queue <Train, vector<Train>, greater<Train> > Tr;
Далее основная логика программы укладывается буквально в несколько строк:
scanf("%d%d",&K,&N);
for(i=1;i<=K;i++) {
Tup.push(i); //изначально все тупики свободны
}
//обрабатываем очередную прибывающую электричку
for(i=1;i<=N;i++) {
scanf("%d%d",&in_time,&out_time);
while ((!Tr.empty())&&(Tr.top().outtime<in_time)) {
//отправляем электрички
t=Tr.top(); Tr.pop();
Tup.push(t.tupik);
}
if(Tup.empty()) {
//свободных тупиков нет: организовать движение нельзя
printf("0 %d",i);
return 0;
}
//ставим электричку в тупик
tu=Tup.top(); Tup.pop();
Tr.push(Train(out_time,tu));
//запоминаем номер тупика для последующего вывода
a[i]=tu;
}
//выводим результат
for(i=1;i<=N;i++) {
printf("%d ",a[i]);
}
(Мы не используем здесь для организации ввода/вывода библиотеку iostream, поскольку это значительно замедлило бы выполнение программы.)
Мы использовали дополнительный массив a для хранения номеров тупиков, в которые прибывают электрички. Мы не можем выводить их сразу, поскольку может оказаться, что по данному расписанию движение организовать нельзя.
Как же устроена priority_queue изнутри и насколько быстро выполняются требуемые операции? Для хранения элементов в очереди с приоритетами используется куча — бинарное дерево, элементы которого расположены специальным образом. Наименьший элемент находится в вершине дерева, а добавление и удаление элемента в куче выполняются за логарифм от общего числа элементов. Таким образом, наше решение будет иметь сложность порядка N log (N+K). Подробнее об этой структуре данных можно прочитать, например, в книге Т. Кормена и др. «Алгоритмы: построение и анализ». Обратите внимание, что ограничения на количество тупиков и количество электричек таковы, что при использовании вместо кучи массива или списка решение будет иметь сложность N(N+K), и не будет работать на больших тестах за указанное время.
Существует также решение, использующее только кучу свободных тупиков. Оно использует предварительную совместную сортировку времен прибытия и отправления всех электричек.